package william.mergesort;

/**
 * @author ZhangShenao
 * @date 2024/1/27
 * @description <a href="https://leetcode.cn/problems/count-of-range-sum/description/">...</a>
 */
public class Leetcode327_区间和的个数 {
    /**
     * 通过前缀和数组的方式
     * 将构造前缀和数组
     * 从头开始,逐一构造子数组
     * 判断子数组的区间和是否在指定范围和,如果在,则累计计数
     * 最后返回计数总数
     */
    public int countRangeSum(int[] nums, int lower, int upper) {
        //边界条件校验
        if (nums == null || nums.length < 1 || lower > upper) {
            return 0;
        }

        //构造前缀和数组
        long[] preSum = buildPreSum(nums);

        int count = 0;

        //从头开始,逐一构造子数组,判断每个子数组区间和是否满足指定条件
        for (int i = 0; i < nums.length; i++) {
            for (int j = i; j < nums.length; j++) {
                //获得区间nums[i,j](i<=j),计算该区间和
                long rangeSum = calcRangeSum(preSum, i, j);

                //区间和满足条件,计数+1
                if (rangeSum >= lower && rangeSum <= upper) {
                    ++count;
                }
            }
        }

        //返回累计计数
        return count;

    }


    /**
     * 构造前缀和数组
     */
    private long[] buildPreSum(int[] nums) {
        int len = nums.length;
        long[] preSum = new long[len];
        for (int i = 0; i < len; i++) {
            if (i == 0) {
                preSum[i] = nums[i];
            } else {
                preSum[i] = preSum[i - 1] + nums[i];
            }
        }

        return preSum;
    }

    /**
     * 计算数组[i,j]范围内的区间和
     */
    private long calcRangeSum(long[] preSum, int i, int j) {
        if (i == 0) {
            return preSum[j];
        }
        return (preSum[j] - preSum[i - 1]);
    }
}
